package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: ZhouBert
 * @date: 2021/3/12
 * @description: 714. 买卖股票的最佳时机含手续费
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
 * {@link A_122_买卖股票的最佳时机II} 跟这道题几乎一样
 */
public class B_714_买卖股票的最佳时机含手续费 {

	public static void main(String[] args) {

	}

	/**
	 * 由于每一次完整的交易都会产生一次手续费，那么就把手续费 放到卖出时进行计算
	 * 由于每一次 dp[i][x] 只与 dp[-1i][x] 有关，所以可以不需要用 dp 数组进行记录。
	 * @param prices
	 * @param fee
	 * @return
	 */
	public int maxProfit(int[] prices, int fee) {
		int len = prices.length;
		int[][] dp = new int[len][2];
		dp[0][0] = -prices[0];
		dp[0][1] = 0;
		for (int i = 1; i < len; i++) {
			dp[i][0] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][0]);
			dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
		}
		return dp[len-1][1];
	}


}
